home *** CD-ROM | disk | FTP | other *** search
/ Ham Radio 2000 / Ham Radio 2000.iso / ham2000 / tcp_ip / os2 / pmnos11s / rspf.c < prev    next >
C/C++ Source or Header  |  1993-07-30  |  59KB  |  1,889 lines
  1. /*             RSPF - Radio Shortest Path First
  2.  * This code may be used for non-commercial purposes only.
  3.  *            Anders Klemets SM0RGV
  4.  * 890918 - Version 2.0
  5.  * 900816 - Version 2.1
  6.  *
  7.  * Mods by PA0GRI
  8.  */
  9. #if defined(OS2)
  10. #include <time.h>
  11. #endif
  12. #include <errno.h>
  13. #include "global.h"
  14. #include "config.h"
  15. #include "mbuf.h"
  16. #include "proc.h"
  17. #include "timer.h"
  18. #include "netuser.h"
  19. #include "internet.h"
  20. #include "pktdrvr.h"
  21. #include "ip.h"
  22. #include "iface.h"
  23. #include "ax25.h"
  24. #include "arp.h"
  25. #include "icmp.h"
  26. #include "socket.h"
  27. #include "rspf.h"
  28.  
  29. extern struct route *rt_lookup __ARGS((int32 target));
  30.  
  31. #ifdef    AX25
  32. extern struct lq *al_lookup __ARGS((struct iface *ifp,char *addr,int sort));
  33. #else
  34. static struct lq *al_lookup __ARGS((struct iface *ifp,char *addr,int sort));
  35. #endif    /* AX25 */
  36.  
  37. struct rspf_stat Rspf_stat;
  38. struct rspfreasm *Rspfreasmq = NULLRREASM;
  39. struct rspfiface *Rspfifaces = NULLRIFACE;
  40. struct rspfadj *Adjs = NULLADJ;
  41. struct rspfrouter *Rspfrouters = NULLRROUTER;
  42. struct mbuf *Rspfinq = NULLBUF;
  43. struct timer Rspfreasmt, Susptimer;
  44. char *Rrh_message = NULLCHAR;
  45. unsigned short Rspfpingmax = 3;
  46. static int Keeprouter = 0;
  47. static int16 Envelopeid = 0;
  48. static int Nrspfproc = 0;
  49. static unsigned char Rspfsubseq = 0;
  50. static short Rspfseq = -32768 + 1;
  51. static char *findlowroute __ARGS((int32 addr,int *low,int add,int32 *resaddr,int *resbits));
  52. static void makeroutes __ARGS((void));
  53. static void partialupdate __ARGS((struct rspfrouter *rr,struct mbuf *bp));
  54. static struct rspfrouter *rr_lookup __ARGS((int32 addr));
  55. static void rr_delete __ARGS((int32 addr));
  56. static struct rspfiface *rtif_lookup __ARGS((int32 addr));
  57. static void rspfcsum __ARGS((struct mbuf **bpp,int32 dest));
  58. static void update_in __ARGS((struct mbuf *bp,int32 addr));
  59. static void node_in __ARGS((struct mbuf *bp,int32 addr,int full));
  60. static void sendonerspf __ARGS((int32 addr,int32 dest));
  61. static void sendtoall __ARGS((struct mbuf *bp,int nodecnt,struct rspfiface *riface));
  62. static int sendupdate __ARGS((struct mbuf *bp,int nodecnt,int32 addr));
  63. static int isnewer __ARGS((short a,short b));
  64. static void del_reasm __ARGS((struct rspfreasm *re));
  65. static void reasmtimeout __ARGS((void *t));
  66. static struct mbuf *rspfreasm __ARGS((struct mbuf *bp,struct rspfpacketh *rph,int32 addr));
  67. static struct mbuf *fragmenter __ARGS((struct mbuf *bp,int nodes,int16 mtu));
  68. static struct mbuf *makeadjupdate __ARGS((int32 addr,struct rspfrouter *rr));
  69. static void pushadj __ARGS((struct mbuf **bpp,int32 addr,int bits));
  70. static void sendrrh __ARGS((struct rspfiface *ri));
  71. static void sendrspf __ARGS((void));
  72. static void goodbadnews __ARGS((struct rspfadj *adj));
  73. static void add_rspfadj __ARGS((struct rspfadj *adj));
  74. static void rspfcheck __ARGS((struct rspfadj *adj));
  75. static void rspfping __ARGS((int oldstate,void *p,void *v));
  76.  
  77. /* IP passes its RSPF packets to this function */
  78. void
  79. rspf_input(iface,ip,bp,rxbroadcast)
  80. struct iface *iface;
  81. struct ip *ip;
  82. struct mbuf *bp;
  83. int rxbroadcast;
  84. {
  85.     struct pseudo_header ph;    /* Pseudo-header for checksumming */
  86.  
  87.     if(bp == NULLBUF)
  88.         return;
  89.     if(Rspfifaces == NULLRIFACE){    /* Rspf main loop is not running */
  90.         free_p(bp);
  91.         return;
  92.     }
  93.     ph.length = ip->length - IPLEN - ip->optlen;
  94.     ph.source = ip->source;
  95.     ph.dest = ip->dest;
  96.     ph.protocol = ip->protocol;
  97.     if(cksum(&ph,bp,ph.length) != 0){
  98.         /* Checksum failed, ignore packet completely */
  99.         free_p(bp);
  100.         ++Rspf_stat.badcsum;
  101.         return;
  102.     }
  103.     bp = pushdown(bp,1 + sizeof(ip->source) + sizeof(iface));
  104.     *bp->data = RSPFE_PACKET;
  105.     memcpy(bp->data + 1,&ip->source,sizeof(ip->source));
  106.     memcpy(bp->data + 1 + sizeof(ip->source),&iface,sizeof(iface));
  107.     enqueue(&Rspfinq,bp);
  108. }
  109.  
  110. /* Main loop in RSPF process */
  111. void
  112. rspfmain(v,v1,v2)
  113. int v;
  114. void *v1,*v2;
  115. {
  116.     union rspf rspf;        /* Internal packet structure */
  117.     struct rspfadj *adj = NULLADJ;    /* Adjacency */
  118.     struct mbuf *bp, *tbp;
  119.     struct rspfiface *riface;
  120.     struct iface *iface;
  121.     struct route *rp;
  122.     int32 source;            /* Source address */
  123.     int cmd;
  124.     
  125.     for(;;) {
  126.          if(Rspfinq == NULLBUF)
  127.           pwait(&Rspfinq);
  128.          bp = dequeue(&Rspfinq);    /* at least 5 bytes */
  129.          cmd = PULLCHAR(&bp);    /* get internal event indicator */
  130.          pullup(&bp,(char *)&source,sizeof(source));
  131.          switch(cmd) {
  132.          case RSPFE_RRH:
  133.           sendrrh((struct rspfiface *)source);
  134.           break;
  135.          case RSPFE_CHECK:
  136.           rspfcheck((struct rspfadj *)source);
  137.           break;
  138.          case RSPFE_UPDATE:
  139.           sendrspf();
  140.           break;
  141.          case RSPFE_ARP:
  142.           adj = (struct rspfadj *) source;
  143.           source = adj->addr;        /* fall through */
  144.          case RSPFE_PACKET:
  145.           pullup(&bp,(char *)&iface,sizeof(iface));
  146.           break;
  147.          }
  148.          if(cmd != RSPFE_PACKET && cmd != RSPFE_ARP)
  149.           continue;
  150.          if(cmd == RSPFE_PACKET && ntohrspf(&rspf,&bp) == -1){
  151.           free_p(bp);
  152.           continue;
  153.          }
  154.          if(iface != NULLIF) {
  155.           for(riface = Rspfifaces; riface != NULLRIFACE; riface =
  156.               riface->next)
  157.                if(riface->iface == iface)
  158.                break;
  159.          } else
  160.           /* fails if there is no route or no RSPF interface */
  161.           riface = rtif_lookup(source);
  162.  
  163.          if(riface == NULLRIFACE) {
  164.           free_p(bp);
  165.           if(cmd == RSPFE_PACKET)
  166.                ++Rspf_stat.norspfiface;
  167.           continue;    /* We do not use RSPF on this interface */
  168.          }
  169.          /* If we dont have an entry in the routing table for this station,
  170.           * or if the entry is less than 32 bits specific or has a higher
  171.           * cost than our new route, and is pointing to the wrong interface,
  172.           * then add a correct, private, route.
  173.           */
  174.          rp = rt_lookup(source);
  175.          if(rp == NULLROUTE || (rp != NULLROUTE && rp->iface !=
  176.             riface->iface && (rp->bits < 32 || rp->metric >
  177.                       riface->quality))){
  178.           rt_add(source,32,0,iface,riface->quality,0,1);
  179.          }
  180.  
  181.          if(cmd == RSPFE_ARP) {
  182.         if(adj != NULLADJ){
  183.           adj->cost = riface->quality;    /* default cost */
  184.           add_rspfadj(adj);
  185.           continue;
  186.         }
  187.          }
  188.          switch(rspf.hdr.type){        /* packet types */
  189.          case RSPF_RRH:
  190.           ++Rspf_stat.rrhin;
  191.           free_p(bp);
  192.           adj = (struct rspfadj *)callocw(1,sizeof(struct rspfadj));
  193.           adj->addr = rspf.rrh.addr;
  194.           adj->seq = rspf.rrh.seq;
  195.           adj->cost = riface->quality;    /* Default cost */
  196.           adj->state = RSPF_TENTATIVE;
  197.           if(rspf.rrh.flags & RSPFMODE)
  198.                adj->tos = DELAY;
  199.           else
  200.                adj->tos = RELIABILITY;
  201.           add_rspfadj(adj);
  202.           break;
  203.          case RSPF_FULLPKT:
  204.           ++Rspf_stat.updatein;
  205.           /* Feed the packet through the reassembly queue */
  206.           if((tbp = rspfreasm(bp,&rspf.pkthdr,source)) != NULLBUF)
  207.                update_in(tbp,source);
  208.           break;
  209.          }
  210.     }
  211. }
  212.  
  213. /* This function is called every time an RRH should be broadcasted.
  214.  * An RRH is sent on the interface given by ri or on every RSPF interface.
  215.  * The broadcast address of the interface must be routed onto the same
  216.  * interface (using a static route for instance) otherwise there will be no
  217.  * RRH sent on that interface.
  218.  */
  219. static void
  220. sendrrh(ri)
  221. struct rspfiface *ri;        /* interface to use, if specified */
  222. {
  223.     struct pseudo_header ph;
  224.     struct mbuf *bp, *data = NULLBUF;
  225.     struct rspfiface *riface;
  226.     struct route *rp;
  227.     struct rrh rrh;
  228.  
  229.     for(riface = Rspfifaces; riface != NULLRIFACE; riface = riface->next) {
  230.      if(ri != NULLRIFACE && riface != ri)
  231.           continue;
  232.      if((rp = rt_lookup(riface->iface->broadcast)) != NULLROUTE &&
  233.         rp->iface == riface->iface){
  234.           rrh.version = RSPF_VERSION;
  235.           rrh.addr = riface->iface->addr;
  236.           ph.length = 0;
  237.           if(Rrh_message != NULLCHAR) {
  238.            data = ambufw(strlen(Rrh_message));
  239.            memcpy(data->data,Rrh_message,strlen(Rrh_message));
  240.            ph.length = data->cnt = strlen(Rrh_message);
  241.           }
  242.           ph.length += RRHLEN;
  243.           ph.source = riface->iface->addr;
  244.           ph.dest = riface->iface->broadcast;
  245.           ph.protocol = RSPF_PTCL;
  246.           /* Start the RRH link level packet counter at 1, since adj->seq
  247.            * is 0 only for ARP generated adjacencies. This is also correct
  248.            * since rawsndcnt will increase by one when the RRH is sent.
  249.            */
  250.           rrh.seq = riface->iface->rawsndcnt + 1;
  251.           /* Default is to use the same mode as the interface */
  252.           if(Rspfownmode == -1)
  253.            rrh.flags = !(riface->iface->flags & CONNECT_MODE);
  254.           else
  255.            rrh.flags = !(Rspfownmode & CONNECT_MODE);
  256.  
  257.           bp = htonrrh(&rrh,data,&ph);
  258.           ++Rspf_stat.rrhout;
  259.           ip_send(riface->iface->addr,riface->iface->broadcast,RSPF_PTCL,
  260.               0,2,bp,0,0,0); /* the ttl will be decremented to 1 */
  261.      }
  262.     }
  263. }
  264.  
  265. /* This function is called whenever an RRH packet has been received or when
  266.  * a new entry is added to the ARP table.
  267.  */
  268. static void
  269. add_rspfadj(adj)
  270. struct rspfadj *adj;
  271. {
  272.     struct rspfadj *oldadj, *tmp;
  273.     struct rspfiface *riface;
  274.     struct arp_tab *atp;
  275.     struct lq *alp;
  276.     int dif, origdif;
  277.  
  278.     if(adj == NULLADJ)
  279.     return;            /* sanity but it happens... */
  280.     /* Find the previous copy of the adjacency, if there was any */
  281.     /* Insert the new adjacency */
  282.     adj->next = Adjs;
  283.     Adjs = adj;
  284.     for(oldadj = Adjs; oldadj->next != NULLADJ; oldadj = oldadj->next)
  285.     if(oldadj->next->addr == adj->addr) {
  286.         tmp = oldadj->next;
  287.         oldadj->next = oldadj->next->next;
  288.         oldadj = tmp;
  289.         break;
  290.     }
  291.  
  292.     if(oldadj->addr != adj->addr || oldadj == adj)
  293.     oldadj = NULLADJ;
  294.  
  295.     /* ARP entries give no sequence number, so save the old one */
  296.     if(oldadj != NULLADJ) {
  297.      if(adj->seq == 0)
  298.           adj->seq = oldadj->seq;
  299.      if(adj->tos == 0)
  300.           adj->tos = oldadj->tos;    /* they give no TOS either */
  301.     }
  302.  
  303.     switch(adj->state) {
  304.     case RSPF_TENTATIVE:
  305.     if(oldadj != NULLADJ) {
  306.          /* If the adjacency was in OK state, it will remain there.
  307.           * An RRH or ARP upcall can never generate an OK -> Tentative
  308.           * transition.
  309.           */
  310.          if(oldadj->state == RSPF_OK)
  311.          adj->state = RSPF_OK;
  312.          adj->okcnt = oldadj->okcnt;
  313.          /* If old state was Bad, don't announce this adjacency until
  314.           * it is known to be OK, to prevent announcing an adjacency
  315.           * with an state transition loop such as OK -> Suspect -> Bad ->
  316.           * Tentative -> Suspect -> Bad -> Tentative -> ...
  317.           */
  318.          if(oldadj->state == RSPF_BAD) {
  319.           adj->okcnt = 0;
  320.           stop_timer(&oldadj->timer);
  321.           /* Enter Suspect state at once, there is no point in
  322.            * dwelling as Tentative.
  323.            */
  324.           rspfcheck(adj);
  325.          } else {
  326.           /* Inherit the old timer */
  327.           adj->timer.func = rspfevent;
  328.           adj->timer.arg = (void *) &adj->timer;
  329.           /* continue where the old timer is stopped */
  330.           adj->timer.duration = oldadj->timer.duration;
  331.           stop_timer(&oldadj->timer);
  332.           /* Set the timer to Suspectimer in the unlikely event that
  333.            * the timer was stopped and oldadj is not Suspect or Bad.
  334.            * Suspect state is dealt with further below.
  335.            */
  336.           if(dur_timer(&adj->timer) == 0L)
  337.                set_timer(&adj->timer,dur_timer(&Susptimer));
  338.           start_timer(&adj->timer);
  339.           set_timer(&adj->timer,dur_timer(&oldadj->timer));
  340.         }
  341.         /* We must now try to figure out from which AX.25 callsign this
  342.          * packet came. Looking at the ARP table may sometimes help.
  343.          */
  344.         if(oldadj->seq != 0 && adj->seq != 0 &&
  345.            (riface = rtif_lookup(adj->addr)) != NULLRIFACE &&
  346.            (atp = arp_lookup(ARP_AX25,adj->addr)) != NULLARP &&
  347.            atp->state == ARP_VALID &&
  348.            (alp = al_lookup(riface->iface,atp->hw_addr,0)) != NULLLQ){
  349.         /* The wrapping of the modulus is taken into account here */
  350.         if(oldadj->seq > (MAXINT16 - 100) && adj->seq < 100)
  351.             origdif = adj->seq + MAXINT16 - oldadj->seq;
  352.         else
  353.             origdif = adj->seq - oldadj->seq;
  354.         if((alp->currxcnt - adj->heard) > (MAXINT16 - 100)
  355.            && adj->seq < 100)
  356.             dif = origdif + MAXINT16 - (alp->currxcnt - adj->heard);
  357.         else
  358.             dif = origdif - (alp->currxcnt - adj->heard);
  359.         adj->heard = alp->currxcnt;    /* Update the counter */
  360.         /* At this point, "origdif" equals the difference in sequence
  361.          * numbers between the two latest RRH packets, i.e. the
  362.          * number of AX.25 frames the station has sent during since
  363.          * the last RRH packet we heard. "dif" equals the number of
  364.          * AX.25 frames that we actually heard from that station
  365.          * during the same period.
  366.          */
  367.         if(origdif > 0 && dif > 0)
  368.             /* This algorithm can be improved, see 2.1 spec */
  369.             adj->cost = riface->quality*2-riface->quality*dif/origdif;
  370.         }
  371.         /* Ignore any new RRH's if a pinger process is already running */
  372.         if(oldadj->state == RSPF_SUSPECT) {
  373.          if(adj->heard != 0)        /* save new heard count */
  374.               oldadj->heard = adj->heard;
  375.          oldadj->next = adj->next;    /* adj is at start of chain */
  376.          Adjs = oldadj;
  377.          stop_timer(&adj->timer);
  378.          free((char *)adj);
  379.          return;
  380.         }
  381.         } else {                    /* oldadj == NULLADJ */
  382.         rspfcheck(adj);            /* enter Suspect state */
  383.         /* A new adjacency may affect the routing table even though no
  384.          * routing updates have yet been received from it.
  385.          */
  386.         makeroutes();
  387.     }
  388.     break;
  389.     case RSPF_OK:
  390.     if(oldadj != NULLADJ) {
  391.         adj->okcnt += oldadj->okcnt;    /* Do these before possible */
  392.         stop_timer(&oldadj->timer);        /* killproc() -- KZ1F */
  393.         if(oldadj->state == RSPF_SUSPECT){
  394.         alert(oldadj->pinger, EABORT);    /* let child terminate itself, kz1f */
  395.         --Nrspfproc;            /* Bug fix - N1BEE */
  396.         }
  397.     }
  398.     else
  399.          makeroutes();            /* routing table may change */
  400.     if(adj->okcnt == 1)            /* A previously unkown route */
  401.         goodbadnews(adj);            /* ..that is good news */
  402.     break;
  403.     }
  404.     if (oldadj != NULLADJ)  /* not necessarily present, kz1f */
  405.     {
  406.     stop_timer(&oldadj->timer); /* This may still have a running timer KZ1F */
  407.     free((char *)oldadj);
  408.     }
  409. #ifndef KZ1F
  410. #endif
  411. }
  412.  
  413. /* Take appropriate action if an adjacency is Bad or Tentative */
  414. static void
  415. rspfcheck(adj)
  416. struct rspfadj *adj;
  417. {
  418.     struct rspfadj *prev;
  419.  
  420.     for(prev = Adjs; prev != NULLADJ; prev = prev->next)
  421.      if(prev->next == adj)
  422.           break;
  423.     switch(adj->state){
  424.     case RSPF_OK:
  425.      adj->state = RSPF_TENTATIVE;     /* note fall-thru */
  426.     case RSPF_TENTATIVE:
  427.      if (Nrspfproc < RSPF_PROCMAX) {
  428.           Nrspfproc++;
  429.           adj->pinger = newproc("RSPF ping",1024,rspfping,
  430.                     (int)adj->state,adj,NULL,0);
  431.           adj->state = RSPF_SUSPECT; /* The adjacency is now Suspect */
  432.      } else {        /* Try later */
  433.           set_timer(&adj->timer,dur_timer(&Susptimer));
  434.           start_timer(&adj->timer);
  435.      }
  436.      break;
  437.     case RSPF_BAD:
  438.          rr_delete(adj->addr);
  439.      adj->cost = 255;
  440.      if(adj->okcnt != 0)
  441.           goodbadnews(adj);        /* This is bad news... */
  442.      if(prev != NULLADJ)
  443.           prev->next = adj->next;    /* Unlink */
  444.      else
  445.           Adjs = adj->next;
  446.      stop_timer(&adj->timer);    /* just in case */
  447.      free((char *)adj);        /* delete the adjacency */
  448.      makeroutes();            /* update the routing table */
  449.      break;
  450.     }
  451. }
  452.  
  453. /* Send a ping to a suspect or tentative adjacency */
  454. static void
  455. rspfping(oldstate, p, v)
  456. int oldstate;
  457. void *p, *v;
  458. {
  459.     int s, fromlen, pcnt;
  460.     struct icmp icmp;
  461.     struct rspfadj *adj;
  462.     struct sockaddr_in from;
  463.     struct mbuf *bp;
  464.  
  465.     pause(((ptol(p) & 7)+1)*1000L);    /* Pause for 1 to 8 seconds */
  466.     adj = (struct rspfadj *) p;
  467.     adj->timer.func = rspfevent;        /* Fill in timer values */
  468.     adj->timer.arg = (void *) &adj->timer;
  469.     set_timer(&adj->timer,dur_timer(&Susptimer));
  470.     if((s = socket(AF_INET,SOCK_RAW,ICMP_PTCL)) == -1){
  471.     --Nrspfproc;
  472.     adj->state = oldstate;
  473.     start_timer(&adj->timer);
  474.     return;
  475.     }
  476.  
  477.     fromlen = sizeof(from);
  478.     for(pcnt=0; pcnt < Rspfpingmax; ++pcnt) {
  479.     pingem(s,adj->addr,0,(int16)s,0);
  480.     /* Now collect the reply */
  481.     alarm(60 * 1000L);/* Let each ping timeout after 60 seconds */
  482.     for(;;) {
  483.          if(recv_mbuf(s,&bp,0,(char *)&from,&fromlen) == -1){
  484.           if(errno == EALARM) /* We timed out */
  485.                break;
  486.           if(errno == EABORT) /* We are no longer needed */
  487.                return;    /* terminate gracefully kz1f */
  488.           alarm(0);
  489.           adj->state = oldstate;
  490.           close_s(s);
  491.           --Nrspfproc;
  492.           start_timer(&adj->timer);
  493.           return;
  494.          }
  495.          ntohicmp(&icmp,&bp);
  496.          free_p(bp);
  497.          if(icmp.type != ICMP_ECHO_REPLY || from.sin_addr.s_addr !=
  498.         adj->addr || icmp.args.echo.id != s)
  499.           /* Ignore other people's responses */
  500.           continue;
  501.          alarm(0);
  502.          if(++adj->okcnt == 1)
  503.           goodbadnews(adj);        /* Good news */
  504.          close_s(s);
  505.          --Nrspfproc;
  506.          start_timer(&adj->timer);
  507.          adj->state = RSPF_OK;        /* Finally change state */
  508.          return;
  509.     }
  510.     }
  511.     /* we give up, mark the adjacency as bad */
  512.     adj->state = RSPF_BAD;
  513.     close_s(s);
  514.     --Nrspfproc;
  515.     start_timer(&adj->timer);
  516. }
  517.  
  518. /* ARP upcalls come in two flavors: When an ARP Reply has been received, we
  519.  * know for certain that bidirectional communication is possible with the
  520.  * particular station. But when an ARP Request is received, or if an ARP
  521.  * entry is added manually, it has yet to be determined if the link is
  522.  * bidirectional so iface is NULLIF in those cases.
  523.  */
  524. void
  525. rspfarpupcall(int32 addr, int16 hardware,struct iface *iface)
  526. {
  527.     struct rspfadj *adj;
  528.     struct mbuf *bp;
  529.     struct rspfiface *riface;
  530.  
  531.     if((riface = rtif_lookup(addr)) == NULLRIFACE)
  532.      return;        /* Not a route to an RSPF interface */
  533.     /* Proceed only if the ARP entry is for a hardware type that is relevant
  534.      * for the interface onto which IP datagrams are routed.
  535.      */
  536.     switch(hardware) {
  537.     case ARP_NETROM:
  538.      if(riface->iface->type != CL_NETROM)
  539.           return;
  540.      break;
  541.     case ARP_AX25:
  542.      if(riface->iface->type != CL_AX25)
  543.           return;
  544.      break;
  545.     case ARP_ETHER:
  546.      if(riface->iface->type != CL_ETHERNET)
  547.           return;
  548.      break;
  549.     case NHWTYPES:
  550.      break;        /* "Any interface type is ok" type entry */
  551.     default:
  552.      return;
  553.     }
  554.     if((adj = (struct rspfadj *)calloc(1,sizeof(struct rspfadj)))==NULLADJ)
  555.     return;
  556.     adj->addr = addr;
  557.     if(iface == NULLIF)      /* A manual ARP entry or Request, may be no-good */
  558.     adj->state = RSPF_TENTATIVE;
  559.     else {
  560.     adj->state = RSPF_OK;
  561.     adj->okcnt++;
  562.     adj->timer.func = rspfevent;        /* Fill in timer values */
  563.     adj->timer.arg = (void *) &adj->timer;
  564.     set_timer(&adj->timer,dur_timer(&Susptimer));
  565.     start_timer(&adj->timer);
  566.     }
  567.     if((bp = alloc_mbuf(1+sizeof(int32)+sizeof(iface))) == NULLBUF) {
  568.      stop_timer(&adj->timer);
  569.      free((char *)adj);
  570.      return;
  571.     }
  572.     *bp->data = RSPFE_ARP;
  573.     memcpy(bp->data + 1, (char *) &adj, sizeof(adj));
  574.     memcpy(bp->data + 1 + sizeof(adj), (char *) &iface, sizeof(iface));
  575.     bp->cnt = bp->size;
  576.     enqueue(&Rspfinq,bp);
  577. }
  578.  
  579. /* Called by "route add" command. */
  580. void
  581. rspfrouteupcall(addr,bits,gateway)
  582. int32 addr;            /* Address added to routing table */
  583. unsigned bits;            /* Significant bits in address */
  584. int32 gateway;            /* Address of gateway station */
  585. {
  586.     /* We are only interested in 32 bit specific routes that use a
  587.      * gateway. Direct routes will be discovered anyway.
  588.      */
  589.     if(bits != 32 || gateway == 0 || gateway == addr)
  590.      return;
  591.     if(rtif_lookup(addr) == NULLRIFACE) /* not routed onto RSPF interface */
  592.      return;
  593.     rspfarpupcall(addr,NHWTYPES,NULLIF); /* proceed as an "arp add" upcall */
  594. }
  595.  
  596. /* When the suspect timer expires, we scan through the routing table for all
  597.  * manual 32 bit specific routes through a gateway that are not an adjacency,
  598.  * and calls rspfrouteupcall(). A similar thing is done for all manual ARP
  599.  * entries. This will make sure that a station that was not reachable when
  600.  * the "route add" or "arp add" command was executed will eventually be
  601.  * discovered if it joins the network.
  602.  */
  603. void
  604. rspfsuspect(t)
  605. void *t;
  606. {
  607.      struct rspfadj *adj;
  608.      struct route *rp;
  609.      struct arp_tab *ap;
  610.      int i;
  611.      start_timer(&Susptimer);            /* restart the timer */
  612.      for(i = 0; i < HASHMOD; i++)        /* Check the routing table */
  613.       for(rp = Routes[31][i]; rp != NULLROUTE; rp = rp->next) {
  614.            if((rp->flags & RTPRIVATE) || dur_timer(&rp->timer) != 0)
  615.             continue;    /* not this route */
  616.            for(adj = Adjs; adj != NULLADJ; adj = adj->next)
  617.             if(adj->addr == rp->target)
  618.              break;
  619.            if(adj == NULLADJ) /* it is not already an adjacency */
  620.             rspfrouteupcall(rp->target,32,rp->gateway);
  621.       }
  622.      for(i=0; i < HASHMOD; ++i)    /* scan the ARP table */
  623.       for(ap = Arp_tab[i]; ap != NULLARP; ap = ap->next) {
  624.            if(dur_timer(&ap->timer))    /* not a manual entry */
  625.             continue;
  626.            for(adj = Adjs; adj != NULLADJ; adj = adj->next)
  627.             if(adj->addr == ap->ip_addr)
  628.              break;
  629.            if(adj == NULLADJ)    /* not already an adjacency */
  630.             rspfarpupcall(ap->ip_addr,ap->hardware,NULLIF);
  631.       }
  632. }
  633.  
  634. /* This non-layered function peeks at the routing table to figure out to which
  635.  * interface datagrams for addr will be routed. Then it returns the matching
  636.  * rspfiface structure.
  637.  */
  638. static
  639. struct rspfiface *
  640. rtif_lookup(addr)
  641. int32 addr;
  642. {
  643.     struct rspfiface *riface;
  644.     struct route *rp;
  645.     if((rp = rt_lookup(addr)) == NULLROUTE)
  646.     return NULLRIFACE;
  647.     riface = Rspfifaces;
  648.     while(riface != NULLRIFACE){
  649.     if(riface->iface == rp->iface)
  650.         return riface;
  651.     riface = riface->next;
  652.     }
  653.     return NULLRIFACE;
  654. }
  655.  
  656. /* Send good or bad news partial routing updates. A cost of 255 should be
  657.  * interpreted as bad news by the remote station.
  658.  */
  659. static void
  660. goodbadnews(adj)
  661. struct rspfadj *adj;
  662. {
  663.     struct rspfnodeh nodeh;
  664.     struct rspflinkh linkh;
  665.     struct rspfiface *riface;
  666.     struct rspfrouter *rr;
  667.     struct mbuf *bp, *tbp, *wbp;
  668.     int nodecnt = 1;
  669.     if((riface = rtif_lookup(adj->addr)) == NULLRIFACE)
  670.     return;
  671.     bp = ambufw(5);
  672.     bp->cnt = bp->size;
  673.     *bp->data = 32;     /* the number of significant bits in the address */
  674.     put32(bp->data+1,adj->addr);
  675.     linkh.horizon = riface->horizon;
  676.     linkh.erp = riface->erp;
  677.     linkh.cost = adj->cost;
  678.     linkh.adjn = 1;
  679.     tbp = htonrspflink(&linkh,bp);
  680.     nodeh.seq = Rspfseq;
  681.     nodeh.subseq = ++Rspfsubseq;
  682.     nodeh.links = 1;
  683.     for(riface = Rspfifaces; riface != NULLRIFACE; riface = riface->next) {
  684.       if(dup_p(&wbp,tbp,0,len_p(tbp)) != len_p(tbp)) {
  685.            free_p(wbp);
  686.            continue;
  687.        }
  688.        nodeh.addr = riface->iface->addr;
  689.        bp = htonrspfnode(&nodeh,wbp);
  690.        sendtoall(bp,1,riface);
  691.     }
  692.     free_p(tbp);
  693.     /* If this is a new adjacency, then send it a routing update immediately */
  694.     if(adj->cost == 255 || adj->okcnt != 1)
  695.     return;
  696.     /* When two RSPF stations learn about each others existence, one of
  697.      * them will usually have received an RRH from the other. The one that
  698.      * received the RRH will send the peer a routing update immediately.
  699.      * So in the code below, if no RRH has been received (seq is 0) and no
  700.      * routing update has yet been received, we should expect to receive a
  701.      * routing update shortly if the adjacency is running RSPF.
  702.      * This could fail though if two RSPF stations learn about each other
  703.      * solely through ARP upcalls and no RRH's or Updates were exchanged
  704.      * prior to or during the establishment of the adjacency.
  705.      */
  706.     if(adj->seq == 0 && rr_lookup(adj->addr) == NULLRROUTER) {
  707.     if(adj->state != RSPF_SUSPECT)    /* running in RSPF process, give up */
  708.         return;
  709.     alarm(15 * 1000);    /* wait for an Update */
  710.     if(pwait(adj) == EALARM)
  711.          return;    /* still no sign of RSPF activity from the adjacency */
  712.     alarm(0);
  713.     }
  714.     ++adj->okcnt;    /* we don't want to get here again */
  715.     if((bp = makeownupdate(adj->addr,1)) == NULLBUF)
  716.     return;
  717.     for(rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next)
  718.     if((tbp = makeadjupdate(get32(rr->data->data),rr)) != NULLBUF){
  719.          append(&bp,tbp);
  720.          nodecnt++;
  721.     }
  722.     sendupdate(bp,nodecnt,adj->addr);
  723. }
  724.  
  725. /* This function is called whenever it is time to send a new RSPF update */
  726. static void
  727. sendrspf()
  728. {
  729.     struct rspfrouter *rr;
  730.     struct mbuf *bp, *wbp, *tmp = NULLBUF;
  731.     struct rspfiface *riface;
  732.     struct rspfadj *adj;
  733.     int nodecnt, incr = 1;
  734.  
  735.     for(nodecnt = 1, rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next)
  736.      if(!rr->sent)        /* don't send stale data */
  737.           if((bp = makeadjupdate(get32(rr->data->data),rr)) != NULLBUF){
  738.            append(&tmp,bp);
  739.            nodecnt++;
  740.           }
  741.     for(riface = Rspfifaces; riface != NULLRIFACE; riface = riface->next) {
  742.      /* Find an address that is routed onto this interface */
  743.      for(adj = Adjs; adj != NULLADJ; adj = adj->next)
  744.           if(rtif_lookup(adj->addr) == riface)
  745.            break;
  746.      if(adj == NULLADJ)    /* no adjacency on that interface? */
  747.           continue;
  748.      if(dup_p(&wbp,tmp,0,len_p(tmp)) != len_p(tmp)) {
  749.           free_p(wbp);
  750.           continue;
  751.      }
  752.      if((bp = makeownupdate(adj->addr,incr)) != NULLBUF) {
  753.           incr = 0;    /* sequence number is incremented only once */
  754.           append(&bp,wbp);
  755.      }
  756.      else
  757.           break;
  758.      sendtoall(bp,nodecnt,riface);
  759.     }
  760.     free_p(tmp);
  761.     for(rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next)
  762.      if(!rr->sent)        /* Mark router data as propagated */
  763.           ++rr->sent;
  764. }
  765.  
  766. /* This function is used to answer "poll" messages */
  767. static void
  768. sendonerspf(addr,dest)
  769. int32 addr;    /* address of station whose routing update we will make */
  770. int32 dest;    /* address of station to send the update to */
  771. {
  772.     struct mbuf *bp;
  773.     if(ismyaddr(addr)){
  774.     if((bp = makeownupdate(dest,0)) == NULLBUF)
  775.         return;
  776.     sendupdate(bp,1,dest);
  777.     return;
  778.     }
  779.     if((bp = makeadjupdate(addr,NULLRROUTER)) == NULLBUF)
  780.     return;
  781.     sendupdate(bp,1,dest);
  782. }
  783.  
  784. /* send an update to all adjacencies on an RSPF interface */
  785. static void
  786. sendtoall(bp,nodecnt,riface)
  787. struct mbuf *bp;
  788. int nodecnt;            /* number of reporting nodes in update */
  789. struct rspfiface *riface;    /* interface to sent to */
  790. {
  791.      struct rspfadj *adj;
  792.      struct mbuf *wbp;
  793.      int broad;
  794.      for(broad = 0, adj = Adjs; adj != NULLADJ; adj = adj->next)
  795.       /* If adj->seq is 0 we have never received an RRH from the
  796.        * adjacency, and if there is no stored routing update, then
  797.        * it is not known if the adjacency understands RSPF.
  798.        */
  799.       if((adj->seq != 0 || rr_lookup(adj->addr) != NULLRROUTER) &&
  800.          riface == rtif_lookup(adj->addr)) {
  801.            if((adj->tos & RELIABILITY) && !(adj->tos & DELAY)) {
  802.             if(dup_p(&wbp,bp,0,len_p(bp)) != len_p(bp)) {
  803.              free_p(wbp);
  804.              continue;
  805.             }
  806.             sendupdate(wbp,nodecnt,adj->addr); /* private copy */
  807.            }
  808.            else
  809.             ++broad;    /* send to broadcast IP address instead */
  810.       }
  811.      if(broad != 0)
  812.       if(dup_p(&wbp,bp,0,len_p(bp)) != len_p(bp))
  813.            free_p(wbp);
  814.       else
  815.            sendupdate(wbp,nodecnt,riface->iface->broadcast);
  816.      free_p(bp);
  817. }
  818.  
  819. /* This function sends a routing update to the adjacencies that we have
  820.  * recevied RRH's from.
  821.  */
  822. static int
  823. sendupdate(bp,nodecnt,addr)
  824. struct mbuf *bp;    /* Full packet, except for the packet header */
  825. int nodecnt;        /* Number of reporting nodes in the packet */
  826. int32 addr;        /* Station to send update to */
  827. {
  828.     struct rspfadj *adj;
  829.     struct mbuf *tmp;
  830.     int tos = 0;
  831.  
  832.     /* See if we are sending to a known adjacency, in use its TOS in
  833.      * that case.
  834.      */
  835.     for(adj = Adjs; adj != NULLADJ; adj = adj->next)
  836.      if(adj->addr == addr) {
  837.           tos = adj->tos;
  838.           break;
  839.      }
  840.     if((tmp = fragmenter(bp,nodecnt,ip_mtu(addr) - IPLEN)) == NULLBUF)
  841.      return -1;
  842.     while((bp = dequeue(&tmp)) != NULLBUF){
  843.      rspfcsum(&bp,addr);    /* Calculate the checksum */
  844.      ++Rspf_stat.updateout;
  845.      ip_send(INADDR_ANY,addr,RSPF_PTCL,INET_CTL | tos,2,bp,0,0,0);
  846.     }
  847.     return 0;
  848. }
  849.  
  850. /* Fragment a large mbuf if necessary into packets of maximum mtu bytes.
  851.  * Each packet is prepended a RSPF routing update header, without the checksum.
  852.  */
  853. static struct mbuf *
  854. fragmenter(struct mbuf *bp, int nodes, int16 mtu)
  855. {
  856.     struct rspfnodeh nodeh;
  857.     struct rspflinkh linkh;
  858.     struct rspfpacketh pkth;
  859.     struct mbuf *tbp, *tmp, *bpq = NULLBUF;
  860.     int n, nodecnt, linkcnt, adjcnt, nodemax, sync;
  861.     char *cp, fragn = 1;
  862.  
  863.     if(mtu < RSPFPKTLEN + RSPFNODELEN || bp == NULLBUF) {
  864.      free_p(bp);
  865.      return NULLBUF;
  866.     }
  867.     ++Envelopeid;
  868.     nodemax = nodes;        /* total number of nodes in envelope */
  869.     nodecnt = nodes;        /* nodes left to packetize */
  870.     linkcnt = adjcnt = 0;
  871.     while(len_p(bp) != 0){
  872.     n = min(mtu,len_p(bp)+RSPFPKTLEN);    /* length of this packet */
  873.     n -= RSPFPKTLEN;
  874.     tbp = NULLBUF;
  875.     sync = 0;
  876.     if(adjcnt){
  877.         tbp = ambufw(min(adjcnt*5,n/5*5));
  878.         tbp->cnt = tbp->size;
  879.         cp = tbp->data;
  880.     }
  881.     while(n > 0){
  882.         while(adjcnt){
  883.         if((n -= 5) < 0)
  884.             break;
  885.         pullup(&bp,cp,5);
  886.         cp += 5;
  887.         adjcnt--;
  888.         }
  889.         if(linkcnt && n > 0){
  890.         if((n -= RSPFLINKLEN) < 0)
  891.             break;
  892.         ntohrspflink(&linkh,&bp);
  893.         adjcnt = linkh.adjn;
  894.         tmp = htonrspflink(&linkh,NULLBUF);
  895.         append(&tbp,tmp);
  896.         tmp = ambufw(min(5*adjcnt,n/5*5));
  897.         tmp->cnt = tmp->size;
  898.         cp = tmp->data;
  899.         append(&tbp,tmp);
  900.         linkcnt--;
  901.         continue;
  902.         }
  903.         if(nodecnt && linkcnt == 0 && n > 0){
  904.         if((n -= RSPFNODELEN) < 0)
  905.             break;
  906.         if(nodecnt == nodes)        /* Set the sync octet */
  907.             sync = len_p(tbp) + 4;
  908.         ntohrspfnode(&nodeh,&bp);
  909.         linkcnt = nodeh.links;
  910.         tmp = htonrspfnode(&nodeh,NULLBUF);
  911.         append(&tbp,tmp);
  912.         nodecnt--;
  913.         }
  914.     }
  915.     pkth.version = RSPF_VERSION;    /* The version number */
  916.     pkth.type = RSPF_FULLPKT;    /* The packet type */
  917.     pkth.fragn = fragn++;        /* The fragment number */
  918.     pkth.fragtot = 0;        /* The total number of fragments */
  919.     pkth.csum = 0;            /* The checksum */
  920.     pkth.sync = sync < 256 ? sync : 0;    /* The sync octet */
  921.     pkth.nodes = nodemax;        /* The number of nodes in envelope */
  922.     pkth.envid = Envelopeid;    /* The envelope-ID */
  923.     tmp = htonrspf(&pkth,tbp);    /* add packet header */
  924.     enqueue(&bpq,tmp);        /* add packet to chain */
  925.     nodes = nodecnt;        /* number of nodes left */
  926.     }
  927.     free_p(bp);
  928.     for(tbp = bpq; tbp != NULLBUF; tbp = tbp->anext)
  929.     *(tbp->data + 3) = len_q(bpq);    /* Set the fragment total counter */
  930.     return bpq;
  931. }
  932.  
  933. /* Calculate the checksum on an RSPF routing update packet */
  934. static void
  935. rspfcsum(bpp,dest)
  936. struct mbuf **bpp;
  937. int32 dest;
  938. {
  939.     struct pseudo_header ph;
  940.     int16 checksum;
  941.     ph.length = len_p(*bpp);
  942.     ph.source = locaddr(dest);
  943.     ph.dest = dest;
  944.     ph.protocol = RSPF_PTCL;
  945.     if((checksum = cksum(&ph,*bpp,ph.length)) == 0)
  946.     checksum = 0xffffffff;
  947.     /* This assumes that the checksum really is at this position */
  948.     put16((*bpp)->data+4,checksum);
  949. }
  950.  
  951. /* This function creates our own routing update and returns it in an mbuf */
  952. struct mbuf *
  953. makeownupdate(dest,new)
  954. int32 dest;        /* Address of a station that will get this update */
  955. int new;        /* True if the sequence number should be incremented */
  956. {
  957.     struct rspfadj *adj;
  958.     struct rspflinkh linkh;
  959.     struct rspfnodeh nodeh;
  960.     struct rspfiface *riface, rifdefault;
  961.     struct mbuf *bp = NULLBUF, *tbp, *tmp;
  962.     struct route *rp;
  963.     int i, adjcnt, lnkcnt, bits;
  964.     int32 prev, low, cur;
  965.  
  966.     /* Set default values to apply to non-RSPF interfaces */
  967.     rifdefault.horizon = 32;
  968.     rifdefault.erp = 0;
  969.     rifdefault.quality = 0;
  970.     /* Our adjacencies has to be sorted into groups of the same horizon,
  971.      * ERP factor and cost. This is done by combining these numbers into a
  972.      * single one, modulo 256 and take the lowest number first.
  973.      */
  974.     low = 0;
  975.     lnkcnt = 0;
  976.     for(;;){
  977.     prev = low;
  978.     low = 255*65536L+255*256+255;
  979.     for(adj = Adjs; adj != NULLADJ; adj = adj->next)
  980.          /* Include all adjacecies that have been or are in OK state
  981.           * in the update. Bad adjacencies are also included to give
  982.           * them a chance to recover. Hopelessly Bad adjacencies are
  983.           * eventually deleted elsewhere.
  984.           */
  985.         if(adj->okcnt != 0 && (riface = rtif_lookup(adj->addr)) !=
  986.            NULLRIFACE) {
  987.         cur = riface->horizon*65536L+riface->erp*256+adj->cost;
  988.         if(cur > prev && cur < low)
  989.             low = cur;
  990.         }
  991.     /* Add any manual public, 1-31 bit specific routes.
  992.      * Use the route metric only if it is greater than the default
  993.      * quality to lessen a possible "wormhole" effect.
  994.      */
  995.     for(bits = 1; bits <= 31; bits++)
  996.         for(i = 0; i < HASHMOD; i++)
  997.         for(rp = Routes[bits-1][i]; rp != NULLROUTE; rp = rp->next)
  998.              if(!(rp->flags & RTPRIVATE) && !dur_timer(&rp->timer)) {
  999.              if((riface = rtif_lookup(rp->target)) == NULLRIFACE)
  1000.                     riface = &rifdefault;
  1001.              cur = riface->horizon*65536L+riface->erp*256+
  1002.                 (rp->metric > riface->quality ? rp->metric :
  1003.                 riface->quality);
  1004.             if(cur > prev && cur < low)
  1005.                 low = cur;
  1006.              }
  1007.     /* Add any 32 bit routes on interfaces not using RSPF */
  1008.     for(i = 0; i < HASHMOD; i++)
  1009.          for(rp = Routes[31][i]; rp != NULLROUTE; rp = rp->next)
  1010.           if(!(rp->flags & RTPRIVATE) && rtif_lookup(rp->target)
  1011.              == NULLRIFACE) {
  1012.                cur = rifdefault.horizon*65536L+rifdefault.erp*256+
  1013.                 (rp->metric > rifdefault.quality ? rp->metric :
  1014.                  rifdefault.quality);
  1015.                if(cur > prev && cur < low)
  1016.                 low = cur;
  1017.           }
  1018.     /* Add the default route */
  1019.     if((rp = rt_blookup(0,0)) != NULLROUTE && !(rp->flags & RTPRIVATE) &&
  1020.        !dur_timer(&rp->timer)) {
  1021.          if((riface = rtif_lookup(0)) == NULLRIFACE)
  1022.           riface = &rifdefault;
  1023.          cur = riface->horizon*65536L+riface->erp*256+
  1024.         (rp->metric > riface->quality ? rp->metric : riface->quality);
  1025.          if(cur > prev && cur < low)
  1026.           low = cur;
  1027.     }
  1028.     if(low == 255*65536L+255*256+255) /* All done */
  1029.         break;
  1030.     /* now start adding the routes */
  1031.     adjcnt = 0;
  1032.     tbp = NULLBUF;
  1033.     for(adj = Adjs; adj != NULLADJ; adj = adj->next)
  1034.         if(adj->okcnt != 0 && (riface = rtif_lookup(adj->addr)) !=
  1035.            NULLRIFACE)
  1036.         if(riface->horizon*65536L+riface->erp*256+adj->cost == low){
  1037.             pushadj(&tbp,adj->addr,32);
  1038.             adjcnt++;
  1039.         }
  1040.     for(bits = 1; bits <= 31; bits++)
  1041.         for(i = 0; i < HASHMOD; i++)
  1042.         for(rp = Routes[bits-1][i]; rp != NULLROUTE; rp = rp->next)
  1043.              if(!(rp->flags & RTPRIVATE) && !dur_timer(&rp->timer)){
  1044.             if((riface = rtif_lookup(rp->target)) == NULLRIFACE)
  1045.                    riface = &rifdefault;
  1046.             /* Manually entered local routes only */
  1047.             if(riface->horizon*65536L+riface->erp*256+
  1048.                (rp->metric > riface->quality ? rp->metric :
  1049.                riface->quality) == low){
  1050.                 pushadj(&tbp,rp->target,bits);
  1051.                 adjcnt++;
  1052.             }
  1053.              }
  1054.     for(i = 0; i < HASHMOD; i++)    /* 32 bit specific routes */
  1055.          for(rp = Routes[31][i]; rp != NULLROUTE; rp = rp->next)
  1056.           if(!(rp->flags & RTPRIVATE) && rtif_lookup(rp->target)
  1057.              == NULLRIFACE)
  1058.                if(rifdefault.horizon*65536L+rifdefault.erp*256+
  1059.               (rp->metric > rifdefault.quality ? rp->metric :
  1060.                rifdefault.quality) == low){
  1061.                 pushadj(&tbp,rp->target,bits);
  1062.                 adjcnt++;
  1063.                }
  1064.     /* Add the default route */
  1065.     if((rp = rt_blookup(0,0)) != NULLROUTE && !(rp->flags & RTPRIVATE) &&
  1066.        !dur_timer(&rp->timer)) {
  1067.          if((riface = rtif_lookup(0)) == NULLRIFACE)
  1068.           riface = &rifdefault;
  1069.          if(riface->horizon*65536L+riface->erp*256+ (rp->metric >
  1070.         riface->quality ? rp->metric : riface->quality) == low){
  1071.           pushadj(&tbp,0,0);
  1072.           adjcnt++;
  1073.          }
  1074.     }
  1075.     if(adjcnt != 0){
  1076.         /* Prepend the link header */
  1077.         linkh.horizon = ((low >> 16) & 255);/* Horizon value */
  1078.         linkh.erp = ((low >> 8) & 255);    /* ERP factor */
  1079.         linkh.cost = (low & 255);        /* Link cost */
  1080.         linkh.adjn = adjcnt;        /* Number of adjacencies */
  1081.         tmp = htonrspflink(&linkh,tbp);
  1082.         append(&bp,tmp);
  1083.         lnkcnt++;
  1084.     }
  1085.     }
  1086.     /* Prepend the node header */
  1087.     if(lnkcnt != 0){
  1088.     /* Set our address to the IP address used on the destinations
  1089.      * interface.
  1090.      */
  1091.     if(dest == INADDR_ANY || (riface = rtif_lookup(dest)) == NULLRIFACE)
  1092.          nodeh.addr = Ip_addr;
  1093.     else
  1094.          nodeh.addr = riface->iface->addr;
  1095.     if(new){    /* increase sequence number, clear subseq. number */
  1096.         if(Rspfseq == 32768 - 2 || Rspfseq == -32768 + 1)
  1097.          Rspfseq = 0;            /* wrap around */
  1098.         else
  1099.          ++Rspfseq;
  1100.         Rspfsubseq = 0;
  1101.     }
  1102.     nodeh.seq = Rspfseq;
  1103.     nodeh.subseq = 0;
  1104.     nodeh.links = lnkcnt;
  1105.     return htonrspfnode(&nodeh,bp);
  1106.     }
  1107.     else {
  1108.     free_p(bp);
  1109.     return NULLBUF;
  1110.     }
  1111. }
  1112. /* Prepends an adjacency to bpp. Allocates bpp in large chunk for efficency */
  1113. static void
  1114. pushadj(bpp,addr,bits)
  1115. struct mbuf **bpp;
  1116. int32 addr;
  1117. int bits;
  1118. {
  1119.      if(bpp == NULLBUFP)
  1120.       return;
  1121.      if(*bpp == NULLBUF) {
  1122.       *bpp = ambufw(60);        /* good for 12 adjacencies */
  1123.       (*bpp)->data += 55;
  1124.       (*bpp)->cnt = 5;
  1125.      }
  1126.      else
  1127.       *bpp = pushdown(*bpp,5);
  1128.      *(*bpp)->data = bits;
  1129.      put32((*bpp)->data+1,addr);
  1130. }
  1131.  
  1132. /* This function returns the latest routing update in network fromat from
  1133.  * the adjacency denoted by addr.
  1134.  */
  1135. static struct mbuf *
  1136. makeadjupdate(addr,rr)
  1137. int32 addr;
  1138. struct rspfrouter *rr;    /* pointer to stored routing entry, if known */
  1139. {
  1140.     struct mbuf *tmp, *tmp2, *tmp3, *bp = NULLBUF;
  1141.     struct rspfnodeh nodeh;
  1142.     struct rspflinkh linkh;
  1143.     int linkcnt = 0;
  1144.     if(rr == NULLRROUTER && (rr = rr_lookup(addr)) == NULLRROUTER)
  1145.     return NULLBUF;
  1146.     if(dup_p(&tmp,rr->data,0,len_p(rr->data)) != len_p(rr->data)) {
  1147.      free_p(tmp);
  1148.      return NULLBUF;
  1149.     }
  1150.     ntohrspfnode(&nodeh,&tmp);             /* Get the node header */
  1151.     while(nodeh.links--){
  1152.     ntohrspflink(&linkh,&tmp);
  1153.     /* Decrement and check the horizon value */
  1154.     if(--linkh.horizon > 0){
  1155.         /* Duplicate the adjacencies */
  1156.         if(dup_p(&tmp2,tmp,0,5*linkh.adjn) != 5*linkh.adjn){
  1157.         free_p(tmp);
  1158.         free_p(tmp2);
  1159.         free_p(bp);
  1160.         return NULLBUF;
  1161.         }
  1162.         /* Prepend the link header */
  1163.         tmp3 = htonrspflink(&linkh,tmp2);
  1164.         append(&bp,tmp3);
  1165.         linkcnt++;
  1166.     }
  1167.     pullup(&tmp,NULLCHAR,5*linkh.adjn); /* Skip the adjacencies */
  1168.     }
  1169.     free_p(tmp);
  1170.     if(linkcnt == 0){         /* No links at all? */
  1171.     free_p(bp);
  1172.     return NULLBUF;
  1173.     }
  1174.     nodeh.subseq = rr->subseq;
  1175.     nodeh.links = linkcnt;
  1176.     /* Prepend the node header */
  1177.     return htonrspfnode(&nodeh,bp);
  1178. }
  1179.  
  1180. /* Returns 1 if sequence number a is newer than b. Sequence numbers start
  1181.  * at -32768 + 1 and then continues with 0 and the positive integer numbers
  1182.  * until reaching 32768 - 2 after which they continue with 0.
  1183.  * Algorithm taken from RFC-1131 but fixed bug when a or b is 0.
  1184.  */
  1185. static int
  1186. isnewer(short a, short b)
  1187. {
  1188.      if((b < 0 && a > b) ||
  1189.     (a >= 0 && b >= 0 &&    /* bug corrected here */
  1190.      (((32768 - 1)/2 > (a-b) && (a-b) > 0) ||
  1191.       (a-b) < -(32768 - 1)/2)))
  1192.       return 1;
  1193.      return 0;
  1194. }
  1195.  
  1196. /* Reassemble possibly fragmented packets into a single large one */
  1197. static struct mbuf *
  1198. rspfreasm(bp,rph,addr)
  1199. struct mbuf *bp;      /* Routing update packet without packet header */
  1200. struct rspfpacketh *rph;  /* Packet header */
  1201. int32 addr;          /* Address of station we got the packet from */
  1202. {
  1203.     union rspf rspf;
  1204.     struct rspfreasm *re, *rtmp;
  1205.     struct mbuf *tbp, *bp1, *bp2;
  1206.     for(re = Rspfreasmq; re != NULLRREASM; re = re->next)
  1207.     if(re->addr == addr){    /* found another fragment */
  1208.         if(dup_p(&tbp,re->data,0,RSPFPKTLEN) != RSPFPKTLEN) {
  1209.          free_p(tbp);
  1210.          free_p(bp);
  1211.          return NULLBUF;
  1212.         }
  1213.         ntohrspf(&rspf,&tbp);    /* get its packet header */
  1214.         if(rph->envid != rspf.pkthdr.envid) {
  1215.          del_reasm(re);        /* an obsolete entry, delete it */
  1216.          break;
  1217.         }
  1218.         /* Now try to find a place where this fragment fits in the chain */
  1219.         bp1 = re->data;
  1220.         bp2 = NULLBUF;
  1221.         while(rph->fragn > rspf.pkthdr.fragn && bp1->anext != NULLBUF){
  1222.         bp2 = bp1;
  1223.         bp1 = bp1->anext;
  1224.         if(dup_p(&tbp,bp1,0,RSPFPKTLEN) != RSPFPKTLEN) {
  1225.              free_p(bp);
  1226.              free_p(tbp);
  1227.              return NULLBUF;
  1228.         }
  1229.         ntohrspf(&rspf,&tbp);
  1230.         }
  1231.         if(rspf.pkthdr.fragn == rph->fragn) {
  1232.          free_p(bp);
  1233.          return NULLBUF;    /* We already had this one */
  1234.         }
  1235.         bp = htonrspf(rph,bp);    /* Put the packet header back on */
  1236.         /* Insert the fragment at the right place in the chain */
  1237.         if(rph->fragn > rspf.pkthdr.fragn){
  1238.         bp1->anext = bp;
  1239.         bp->anext = NULLBUF;
  1240.         }
  1241.         else {
  1242.         if(bp2 != NULLBUF)
  1243.             bp2->anext = bp;
  1244.         else
  1245.             re->data = bp;
  1246.         bp->anext = bp1;
  1247.         }
  1248.         if(len_q(re->data) == rspf.pkthdr.fragtot){
  1249.         bp1 = NULLBUF;            /* we have all the fragments */
  1250.         while((bp2 = dequeue(&re->data)) != NULLBUF){
  1251.             pullup(&bp2,NULLCHAR,RSPFPKTLEN); /* strip the headers */
  1252.             append(&bp1,bp2);        /* and form a single packet */
  1253.         }
  1254.         del_reasm(re);
  1255.         stop_timer(&Rspfreasmt);
  1256.         reasmtimeout(NULL);    /* restarts timer if necessary */
  1257.         return bp1;        /* return the completed packet */
  1258.         }
  1259.         re->time = secclock();        /* Update the timestamp */
  1260.         goto timstart;        /* We have to wait for fragments */
  1261.     }
  1262.     /* At this point we know that there is no matching entry in the
  1263.        reassembly queue (any more) */
  1264.     if(rph->fragtot == 1)    /* Simple case, an un-fragmented packet */
  1265.     return bp;
  1266.     tbp = htonrspf(rph,bp);    /* Put the packet header back on */
  1267.     rtmp = (struct rspfreasm *) callocw(1,sizeof(struct rspfreasm));
  1268.     /* The values are filled in */
  1269.     rtmp->addr = addr;
  1270.     rtmp->time = secclock();
  1271.     rtmp->data = tbp;
  1272.     rtmp->next = Rspfreasmq;
  1273.     Rspfreasmq = rtmp;
  1274.  timstart:                    /* Start the timer if needed */
  1275.     if(!run_timer(&Rspfreasmt)){
  1276.     Rspfreasmt.func = reasmtimeout;
  1277.     Rspfreasmt.arg = NULL;
  1278.     set_timer(&Rspfreasmt,RSPF_RTIME*1000L); /* The reassembly timeout */
  1279.     start_timer(&Rspfreasmt);
  1280.     }
  1281.     return NULLBUF;
  1282. }
  1283.  
  1284. /* Delete a reassembly descriptor from the queue */
  1285. static void
  1286. del_reasm(re)
  1287. struct rspfreasm *re;
  1288. {
  1289.     struct rspfreasm *r, *prev = NULLRREASM;
  1290.     for(r = Rspfreasmq; r != NULLRREASM; prev = r, r = r->next)
  1291.     if(r == re){
  1292.         free_q(&re->data);
  1293.         if(prev != NULLRREASM)
  1294.         prev->next = re->next;
  1295.         else
  1296.         Rspfreasmq = re->next;
  1297.         free((char *)re);
  1298.         break;
  1299.     }
  1300. }
  1301.  
  1302. /* When the reassembly timer times out, this function tries to make use of
  1303.  * any fragments in the reassembly queue.
  1304.  */
  1305. static void
  1306. reasmtimeout(t)
  1307. void *t;
  1308. {
  1309.     union rspf rspf;
  1310.     struct rspfreasm *re;
  1311.     struct mbuf *bp, *tbp;
  1312.     int last = 0;
  1313.     int32 low;
  1314.     re = Rspfreasmq;
  1315.     while(re != NULLRREASM)
  1316.     if((secclock() - re->time) >= RSPF_RTIME){
  1317.         /* Try to use what we have */
  1318.         bp = NULLBUF;
  1319.         while((tbp = dequeue(&re->data)) != NULLBUF){
  1320.         ntohrspf(&rspf,&tbp);
  1321.         if(rspf.pkthdr.fragn != (last+1)){  /* a missing fragment */
  1322.             if(bp != NULLBUF)
  1323.             update_in(bp,re->addr);
  1324.             bp = NULLBUF;
  1325.             if(rspf.pkthdr.sync != 0)
  1326.             pullup(&tbp,NULLCHAR,rspf.pkthdr.sync - 4);
  1327.             else {    /* no sync possible in this fragment */
  1328.              free_p(tbp);
  1329.              continue;
  1330.             }
  1331.         }
  1332.         append(&bp,tbp);
  1333.         last = rspf.pkthdr.fragn;
  1334.         }
  1335.         if(bp != NULLBUF)
  1336.         update_in(bp,re->addr);
  1337.         del_reasm(re);
  1338.         re = Rspfreasmq;    /* start over again */
  1339.         }
  1340.     else
  1341.          re = re->next;
  1342.     /* Find the oldest fragment and restart the reassembly timer */
  1343.     low = 0;
  1344.     for(re = Rspfreasmq; re != NULLRREASM; re = re->next)
  1345.     if(re->time < low || low == 0)
  1346.         low = re->time;
  1347.     if(low){
  1348.     set_timer(&Rspfreasmt,RSPF_RTIME*1000L - clock() + low);
  1349.     if(dur_timer(&Rspfreasmt) > 0) /* just to be safe */
  1350.         start_timer(&Rspfreasmt);
  1351.     }
  1352. }
  1353.  
  1354. /* Handle incoming routing updates (a reassembled envelope) */
  1355. static void
  1356. update_in(bp,addr)
  1357. struct mbuf *bp;    /* Reassembled data packet, without packet header */
  1358. int32 addr;        /* Senders address (in host order) */
  1359. {
  1360.     struct rspfnodeh nodeh;
  1361.     struct rspflinkh linkh;
  1362.     struct rspfadj *adj;
  1363.     struct mbuf *tbp, *tmp, *b;
  1364.     int linkcnt = 0, adjcnt = 0;
  1365.     int16 offset = 0;
  1366.     tbp = b = NULLBUF;
  1367.     /* Check to see if the sender is an adjacency */
  1368.     for(adj = Adjs; adj != NULLADJ; adj = adj->next)
  1369.      if(adj->addr == addr)
  1370.           break;
  1371.     /* One may argue that updates from non-adjacencies should not be
  1372.      * accepted since they will not contribute to the routing table.
  1373.      * But it might happen that the sender will very shortly become an
  1374.      * adjacency, and then its routing update will come handy. By increasing
  1375.      * Keeprouter, routing updates from disjoint routers will not be not be
  1376.      * purged when makeroutes() is called this time.
  1377.      */
  1378.     if(adj == NULLADJ) {
  1379.      ++Rspf_stat.noadjupdate;
  1380.      Keeprouter += 2;
  1381.     }
  1382.     else
  1383.     psignal(adj,1);        /* alert anyone waiting for the update */
  1384.     while(offset < len_p(bp)){
  1385.     if(adjcnt){
  1386.         if(dup_p(&tmp,bp,offset,5) == 5){
  1387.         append(&tbp,tmp);
  1388.         offset += 5;
  1389.         adjcnt--;
  1390.         continue;
  1391.         }
  1392.         else break;
  1393.     }
  1394.     if(tbp != NULLBUF){
  1395.         tmp = htonrspflink(&linkh,tbp);
  1396.         append(&b,tmp);
  1397.         tbp = NULLBUF;
  1398.     }
  1399.     if(linkcnt){
  1400.         if(dup_p(&tbp,bp,offset,RSPFLINKLEN) == RSPFLINKLEN){
  1401.         ntohrspflink(&linkh,&tbp);
  1402.         adjcnt = linkh.adjn;
  1403.         offset += RSPFLINKLEN;
  1404.         linkcnt--;
  1405.         continue;
  1406.         }
  1407.         else
  1408.         break;
  1409.     }
  1410.     if(b != NULLBUF){
  1411.         tmp = htonrspfnode(&nodeh,b);
  1412.         node_in(tmp,addr,1);     /* a full router update */
  1413.         b = NULLBUF;
  1414.     }
  1415.     if(dup_p(&tmp,bp,offset,RSPFNODELEN) == RSPFNODELEN){
  1416.         ntohrspfnode(&nodeh,&tmp);
  1417.         linkcnt = nodeh.links;
  1418.         offset += RSPFNODELEN;
  1419.     }
  1420.     else {
  1421.          free_p(bp);
  1422.          free_p(tmp);
  1423.          return;
  1424.     }
  1425.     }
  1426.     if(tbp != NULLBUF){
  1427.     /* adjust the adjacency counter in the link header */
  1428.     linkh.adjn -= adjcnt;
  1429.     tmp = htonrspflink(&linkh,tbp);
  1430.     append(&b,tmp);
  1431.     }
  1432.     /* adjust the link counter in the node header */
  1433.     nodeh.links -= linkcnt;
  1434.     tmp = htonrspfnode(&nodeh,b);
  1435.     free_p(bp);
  1436.     if(linkcnt || adjcnt)
  1437.     node_in(tmp,addr,0);     /* a partial router update */
  1438.     else
  1439.     node_in(tmp,addr,1);
  1440. }
  1441.     
  1442. static void
  1443. node_in(bp,addr,full)
  1444. struct mbuf *bp;    /* A single update, starting with the node header */
  1445. int32 addr;        /* Address of station we got packet from */
  1446. int full;        /* False if we got a partial update */
  1447. {
  1448.     struct mbuf *tbp;
  1449.     struct rspfnodeh nodeh, rnodeh;
  1450.     struct rspfrouter *rr;
  1451.     if(dup_p(&tbp,bp,0,RSPFNODELEN) != RSPFNODELEN) {
  1452.      free_p(bp);
  1453.      free_p(tbp);
  1454.      return;
  1455.     }
  1456.     ntohrspfnode(&nodeh,&tbp);
  1457.     if(ismyaddr(nodeh.addr)){
  1458.     /* If another station thinks our routing update sequence number is
  1459.      * larger than it really is, this might be because we have had
  1460.      * a fast system reset and routing updates from the old "epoch"
  1461.      * are still present in the network.
  1462.      */
  1463.     if(isnewer(nodeh.seq,Rspfseq)) {
  1464.         Rspfseq = nodeh.seq + 1;              /* Catch up */
  1465.         if(nodeh.seq == 32768 - 2 || nodeh.seq == -32768 + 1)
  1466.          Rspfseq = 0;                /* Wrap around */
  1467.         sendonerspf(nodeh.addr,addr); /* Send him the latest packet */
  1468.     }
  1469.     free_p(bp);         /* We already know our own adjacencies! */
  1470.     return;
  1471.     }
  1472.     if((rr = rr_lookup(nodeh.addr)) != NULLRROUTER) {
  1473.     if(dup_p(&tbp,rr->data,0,RSPFNODELEN) != RSPFNODELEN) {
  1474.         free_p(bp);
  1475.         free_p(tbp);
  1476.         return;
  1477.         }
  1478.     ntohrspfnode(&rnodeh,&tbp);
  1479.     if(nodeh.seq == rnodeh.seq && nodeh.subseq <= rr->subseq){
  1480.         free_p(bp);
  1481.         return;    /*  We already have this one */
  1482.     }
  1483.     if(isnewer(rnodeh.seq,nodeh.seq)){
  1484.         /* Send him the latest packet */
  1485.         sendonerspf(nodeh.addr,addr);
  1486.         free_p(bp);
  1487.         ++Rspf_stat.oldreport;
  1488.         return;
  1489.     }
  1490.     if(nodeh.subseq > rr->subseq && nodeh.seq == rnodeh.seq){
  1491.         rr->subseq = nodeh.subseq;
  1492.         partialupdate(rr,bp);
  1493.         makeroutes();
  1494.         return;
  1495.     }
  1496.     if(isnewer(nodeh.seq,rnodeh.seq) && !full){
  1497.         partialupdate(rr,bp);
  1498.         makeroutes();
  1499.         /* Send a "poll" packet */
  1500.         --nodeh.seq;
  1501.         nodeh.subseq = 0;
  1502.         nodeh.links = 0;
  1503.         tbp = htonrspfnode(&nodeh,NULLBUF);
  1504.         sendupdate(tbp,1,addr);
  1505.         ++Rspf_stat.outpolls;
  1506.         return;
  1507.     }
  1508.     }
  1509.     else {
  1510.     rr = (struct rspfrouter *) callocw(1,sizeof(struct rspfrouter));
  1511.     rr->next = Rspfrouters;
  1512.     Rspfrouters = rr;
  1513.     }
  1514.     free_p(rr->data);
  1515.     rr->data = bp;
  1516.     rr->subseq = nodeh.subseq;
  1517.     rr->time = secclock();
  1518.     rr->sent = 0;
  1519.     makeroutes();
  1520.     return;
  1521. }
  1522.  
  1523. /* Return the matching RSPF route entry for addr (in host order) */
  1524. static struct rspfrouter *
  1525. rr_lookup(addr)
  1526. int32 addr;
  1527. {
  1528.     struct rspfrouter *rr;
  1529.     for(rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next)
  1530.     /* this assumes that the first word of the header is the address */
  1531.     if(rr->data != NULLBUF && get32(rr->data->data) == addr)
  1532.         return rr;
  1533.     return NULLRROUTER;
  1534. }
  1535.  
  1536. /* Delete the route entry for address addr */
  1537. static void
  1538. rr_delete(addr)
  1539. int32 addr;
  1540. {
  1541.     struct rspfrouter *rr, *prev = NULLRROUTER;
  1542.     for(rr = Rspfrouters; rr != NULLRROUTER; prev = rr, rr = rr->next)
  1543.     /* this assumes that the first word of the header is the address */
  1544.     if(rr->data != NULLBUF && get32(rr->data->data) == addr) {
  1545.          if(prev != NULLRROUTER)
  1546.           prev->next = rr->next;
  1547.          else
  1548.           Rspfrouters = rr->next;
  1549.          free_p(rr->data);
  1550.          free((char *)rr);
  1551.          return;
  1552.     }
  1553. }
  1554.  
  1555. /* Handle incoming partial routing updates. Adjacencies from bp will be
  1556.  * merged into rr->data
  1557.  */
  1558. static void
  1559. partialupdate(rr,bp)
  1560. struct rspfrouter *rr;     /* current node entry in routing table */
  1561. struct mbuf *bp;    /* data packet, starting with node header */
  1562. {
  1563.     struct rspflinkh linkh, rlinkh;
  1564.     struct rspfnodeh rnodeh;
  1565.     struct mbuf *wbp, *tbp, *tmp, *b;
  1566.     int adjcnt = 0, radjcnt, rlinkcnt = 0, bits, rbits, added = 0;
  1567.     int32 addr, raddr;
  1568.  
  1569.     rlinkh.adjn = 0;
  1570.     rr->time = secclock();
  1571.     rr->sent = 0;
  1572.     /* Make a working copy of the stored routing update */
  1573.     if(dup_p(&wbp,rr->data,0,len_p(rr->data)) != len_p(rr->data)) {
  1574.      free_p(wbp);
  1575.      free_p(bp);
  1576.      return;
  1577.     }
  1578.     ntohrspfnode(&rnodeh,&wbp);
  1579.     pullup(&bp,NULLCHAR,RSPFNODELEN);    /* Strip off the node header */
  1580.     while(len_p(bp) > 0)
  1581.     if(adjcnt == 0) {
  1582.          if(ntohrspflink(&linkh,&bp) == -1) {
  1583.           free_p(wbp);
  1584.           free_p(bp);
  1585.           return;
  1586.          }
  1587.          adjcnt = linkh.adjn;
  1588.     }
  1589.     else {
  1590.         bits = PULLCHAR(&bp);    /* get one adjacency to merge */
  1591.         if(pullup(&bp,(char *)&addr,4) != 4) {
  1592.          free_p(wbp);
  1593.          free_p(bp);
  1594.          return;
  1595.         }
  1596.         addr = get32((char *)&addr); /* convert to host order */
  1597.         --adjcnt;
  1598.         radjcnt = 0;
  1599.         b = tbp = NULLBUF;
  1600.         for(;;) {            /* search through stored update */
  1601.         if(radjcnt == 0 || len_p(wbp) == 0) {
  1602.              if(tbp != NULLBUF){
  1603.               rlinkh.adjn -= radjcnt;
  1604.               tmp = htonrspflink(&rlinkh,tbp);
  1605.               ++rlinkcnt;
  1606.               append(&b,tmp);
  1607.               tbp = NULLBUF;
  1608.              }
  1609.              if(len_p(wbp) == 0)
  1610.               break;
  1611.         }
  1612.         if(radjcnt == 0) {
  1613.              ntohrspflink(&rlinkh,&wbp);
  1614.              radjcnt = rlinkh.adjn;
  1615.              if(rlinkh.horizon == linkh.horizon && rlinkh.cost ==
  1616.             linkh.cost && rlinkh.erp == linkh.erp) {
  1617.               pushadj(&tbp,addr,bits);
  1618.               ++rlinkh.adjn;
  1619.               added = 1;
  1620.              }
  1621.         }
  1622.         else {
  1623.             rbits = PULLCHAR(&wbp);
  1624.             raddr = pull32(&wbp);
  1625.             --radjcnt;
  1626.             if(bits != rbits || addr != raddr)
  1627.             pushadj(&tbp,raddr,rbits);    /* Put it back */
  1628.             else
  1629.              --rlinkh.adjn;    /* deleted one adjacency */
  1630.             }
  1631.         }
  1632.         wbp = b;    /* wbp now keeps link headers and adjacencies */
  1633.         if(linkh.cost < 255 && !added){ /* Append the new link */
  1634.         ++rnodeh.links;         /* We will add one extra link */
  1635.         tmp = ambufw(5);
  1636.         *tmp->data = bits;
  1637.         put32(tmp->data+1,addr);
  1638.         tmp->cnt = tmp->size;
  1639.         tbp = htonrspflink(&linkh,tmp);
  1640.         append(&wbp,tbp);
  1641.         }
  1642.         added = 0;
  1643.         }
  1644.    free_p(rr->data);
  1645.    rnodeh.links = rlinkcnt;
  1646.    rr->data = htonrspfnode(&rnodeh,wbp);
  1647. }
  1648.  
  1649. /* The shortest path first algorithm */
  1650. static void
  1651. makeroutes()
  1652. {
  1653.     int bits, i, low, adjcnt;
  1654.     struct mbuf *bp;
  1655.     struct route *rp, *rp2, *saved[HASHMOD];
  1656.     struct rspfadj *adj, *lowadj, *gateway;
  1657.     char *lowp, *r;
  1658.     int32 lowaddr;
  1659.     struct rspflinkh linkh;
  1660.     struct rspfrouter *rr, *rrprev;
  1661.  
  1662.     if(Keeprouter)    /* if false, purge unreachable router entries */
  1663.      --Keeprouter;
  1664.     /* Before we change anything in the routing table, we have to save
  1665.      * each local adjacencies riface pointer
  1666.      */
  1667.     for(adj = Adjs; adj != NULLADJ; adj = adj->next)
  1668.     adj->scratch = (void *) rtif_lookup(adj->addr);
  1669.     /* Remove all non-manual routes */
  1670.     for(bits = 1; bits <= 32; bits++)
  1671.     for(i = 0; i < HASHMOD; i++)
  1672.         for(rp = Routes[bits-1][i]; rp != NULLROUTE; rp = rp->next)
  1673.         if(dur_timer(&rp->timer) != 0)
  1674.             rt_drop(rp->target,bits);
  1675.  
  1676.     if((rp = rt_blookup(0,0)) != NULLROUTE && dur_timer(&rp->timer) != 0)
  1677.      rt_drop(0,0);    /* delete non-manual default route */
  1678.  
  1679.     /* Temporarily remove all 32-bit specific manual routes. This will make
  1680.      * it possible to prevent loops in findlowroute()
  1681.      */
  1682.     for(i = 0; i < HASHMOD; i++) {
  1683.     saved[i] = Routes[31][i];
  1684.     Routes[31][i] = NULLROUTE;
  1685.     }
  1686.  
  1687.     for(;;) {
  1688.     lowadj = NULLADJ;
  1689.     lowp = NULLCHAR;
  1690.     low = 255;
  1691.     for(adj = Adjs; adj != NULLADJ; adj = adj->next){
  1692.        if(adj->scratch == NULL)
  1693.         continue;        /* skip unreachable adjacency */
  1694.         if(!adj->added){
  1695.         if(adj->cost <= low){
  1696.             low = adj->cost;
  1697.             lowadj = adj;
  1698.             lowp = NULLCHAR;
  1699.         }
  1700.         }
  1701.         else
  1702.         if((r = findlowroute(adj->addr,&low,adj->cost,&lowaddr,&bits))
  1703.           != NULLCHAR) {
  1704.             lowp = r;
  1705.             gateway = adj;
  1706.             lowadj = NULLADJ;
  1707.             }
  1708.     }
  1709.     if(lowadj != NULLADJ){
  1710.         lowadj->added++;
  1711.         rp = rt_add(lowadj->addr,32,0,
  1712.            ((struct rspfiface *)lowadj->scratch)->iface,
  1713.            (int32)lowadj->cost,0,0);
  1714.         /* set the timer to a dummy value. This makes it possible to
  1715.          * distinguish between manual and RSPF-generated routes.
  1716.          * The timer is never started however since RSPF handles the
  1717.          * expiration of routes itself.
  1718.          */
  1719.         if (rp != NULLROUTE)    /* it could go NULL, kz1f */
  1720.         set_timer(&rp->timer,MSPTICK);
  1721.         continue;
  1722.     }
  1723.     if(lowp != NULLCHAR){
  1724.         /* Check if we already have this one */
  1725.         rp = rt_blookup(lowaddr,bits);
  1726.         if((rp == NULLROUTE || (rp != NULLROUTE &&
  1727.             rp->metric > (int32) low)) && !ismyaddr(lowaddr)) {
  1728.          /* This is a new route, or a route with strict lower cost than
  1729.           * the previous route (possible only if it was manual)
  1730.           */
  1731.         rp = rt_add(lowaddr,bits,gateway->addr,
  1732.                ((struct rspfiface *)gateway->scratch)->iface,
  1733.                (int32)low,0,0);
  1734.         set_timer(&rp->timer,MSPTICK); /* a dummy value */
  1735.         }
  1736.         *lowp |= 128; /* mark the route as added in any case */
  1737.     }
  1738.     else
  1739.         break; /* no more routes */
  1740.     }
  1741.  
  1742.     /* Add the saved 32 bit routes, if there isn't now a better route */
  1743.     for(i = 0; i < HASHMOD; i++) {
  1744.     rp = saved[i];
  1745.     while(rp != NULLROUTE) {
  1746.          rp2 = rt_blookup(rp->target,32);
  1747.          if(rp2 == NULLROUTE || (rp2 != NULLROUTE && rp2->metric >= rp->metric)) {
  1748.           rp2 = rt_add(rp->target,32,rp->gateway,rp->iface,rp->metric,
  1749.                    0,rp->flags & RTPRIVATE);
  1750.           rp2->uses = rp->uses;
  1751.          }
  1752.          rp2 = rp->next;
  1753.          stop_timer(&rp->timer); /* Stop timer before free() -- KZ1F */
  1754. #ifndef KZ1F
  1755.          free((char *)rp);
  1756. #endif
  1757.          rp = rp2;
  1758.     }
  1759.     }
  1760.  
  1761.     /* Reset all flags */
  1762.     for(adj = Adjs; adj != NULLADJ; adj = adj->next) {
  1763.     adj->added = 0;
  1764.     adj->scratch = NULL;
  1765.     }
  1766.  
  1767.     for(rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next){
  1768.     i = len_p(rr->data) - RSPFNODELEN;
  1769.     /* jump past the node header */
  1770.     if(dup_p(&bp,rr->data,RSPFNODELEN,i) != i) {
  1771.          free_p(bp);
  1772.          continue;
  1773.     }
  1774.     adjcnt = 0;
  1775.     while(i > 0){
  1776.         if(adjcnt){
  1777.         if(!Keeprouter && (*bp->data & 128) == 0) {
  1778.              /* This router has an adjacency that was not added. That
  1779.               * means that the router is unreachable. Mark the
  1780.               * stored routing update for deletion.
  1781.               */
  1782.              free_p(bp);
  1783.              free_p(rr->data);
  1784.              rr->data = NULLBUF;    /* indicates disposal */
  1785.              break;
  1786.         }
  1787.         *bp->data &= ~128;    /* Clear the "added" bit */
  1788.         pullup(&bp,NULLCHAR,5);
  1789.         i -= 5;
  1790.         --adjcnt;
  1791.         continue;
  1792.         }
  1793.         ntohrspflink(&linkh,&bp);
  1794.         adjcnt = linkh.adjn;
  1795.         i -= RSPFLINKLEN;
  1796.         }
  1797.     }
  1798.  
  1799.     if(Keeprouter)    /* nothing more to do */
  1800.      return;
  1801.     /* Delete any routers that were discovered as being unreachable */
  1802.     rrprev = NULLRROUTER;
  1803.     rr = Rspfrouters;
  1804.     for(;;) {
  1805.      for(rrprev = NULLRROUTER, rr = Rspfrouters; rr != NULLRROUTER;
  1806.          rrprev = rr, rr = rr->next)
  1807.           if(rr->data == NULLBUF) {
  1808.            if(rrprev != NULLRROUTER)
  1809.             rrprev->next = rr->next;
  1810.            else
  1811.             Rspfrouters = rr->next;
  1812.            free((char *)rr);
  1813.            break;
  1814.           }
  1815.      if(rr == NULLRROUTER)
  1816.           break;
  1817.     }
  1818. }
  1819.  
  1820. /* Find a route from addr with the lowest cost. Returns a pointer to the
  1821.  * buffer that keeps the significant bit count of the selected route.
  1822.  */
  1823. static char *
  1824. findlowroute(addr,low,add,resaddr,resbits)
  1825. int32 addr;            /* The node whose routes will be examined */
  1826. int *low;            /* Lowest cost so far */
  1827. int add;            /* Cost of this node */
  1828. int32 *resaddr;            /* Resulting route stored here */
  1829. int *resbits;            /* Significant bits of resulting route */
  1830. {
  1831.     struct mbuf *bp;
  1832.     struct rspfrouter *rr;
  1833.     struct rspflinkh linkh;
  1834.     struct route *rp;
  1835.     char *r, *retval = NULLCHAR;
  1836.     int adjcnt = 0;
  1837.  
  1838.     linkh.cost = 0;
  1839.     if((rr = rr_lookup(addr)) == NULLRROUTER)
  1840.     return NULLCHAR;
  1841.     if((rp = rt_blookup(addr,32)) != NULLROUTE && rp->metric < add)
  1842.      return NULLCHAR;    /* already added this one, no loops thanks */
  1843.     if(dup_p(&bp,rr->data,RSPFNODELEN,len_p(rr->data) - RSPFNODELEN) !=
  1844.        len_p(rr->data) - RSPFNODELEN) {
  1845.      free_p(bp);
  1846.      return NULLCHAR;
  1847.     }
  1848.     while(len_p(bp) > 0){
  1849.     if(adjcnt){
  1850.         if(*bp->data & 128) {
  1851.         (void) PULLCHAR(&bp);
  1852.         if((r = findlowroute(pull32(&bp),low,add+linkh.cost,resaddr,
  1853.           resbits)) != NULLCHAR)
  1854.              retval = r;
  1855.         }
  1856.         else {
  1857.         *low = add + linkh.cost;
  1858.         retval = bp->data;
  1859.         *resbits = PULLCHAR(&bp);
  1860.         *resaddr = pull32(&bp);
  1861.         pullup(&bp,NULLCHAR,5*(adjcnt-1));
  1862.         adjcnt = 1;    /* No need to check the rest of this link */
  1863.         }
  1864.         --adjcnt;
  1865.         continue;
  1866.     }
  1867.     ntohrspflink(&linkh,&bp);
  1868.     if((add + linkh.cost) <= *low)
  1869.         adjcnt = linkh.adjn;
  1870.     else
  1871.         pullup(&bp,NULLCHAR,5*linkh.adjn);
  1872.     }
  1873.     return retval;
  1874. }
  1875.  
  1876. #ifndef    AX25
  1877. /*
  1878.  * Dummy stub for RSPF if AX25 is not configured.
  1879.  */
  1880. static struct lq *
  1881. al_lookup(ifp,addr,sort)
  1882. struct iface *ifp;
  1883. char *addr;
  1884. int sort;
  1885. {
  1886.     return NULLLQ;
  1887. }
  1888. #endif    /* AX25 */
  1889.